import UIKit

//算法图解练习

// MARK: - 递归相关

//递归快排
/*
 1. 确定基线条件
 2. 递归
    1.取出数组第一个元素pivot，创建less，more数组
    2.遍历随后元素，current < pivot，加入less中，否则加入more中
    3.递归合并， less pivote more
 */
func quickSort(arr: inout Array<Int>) -> Array<Int> {
    if arr.count < 2 {//基线条件
        return arr
    }else{//递归条件
        let pivot = arr.first!
        var less = [Int]()
        var more = [Int]()
        for i in 1..<arr.count {
            let current = arr[i]
            if current < pivot {
                less.append(current)
            }else{
                more.append(current)
            }
        }
        return quickSort(arr: &less) + [pivot] + quickSort(arr: &more)
    }
}
var quickArr = [3,4,6,1,5,6,7,6,99,11,56]
quickSort(arr: &quickArr)

//递归数组求和
/*
 1. 确认基线条件，如果count == 1，返回第一个元素
 2. 取出第一个元素，然后移除
 3. 递归
 */
func arraySum(arr: inout Array<Int>) -> Int{
    if arr.count == 1 {
        return arr.first!
    }else{
        let first = arr.first!
        arr.removeFirst()
        return first + arraySum(arr: &arr)
    }
}
var arr = [2,5,8,100]
arraySum(arr: &arr)


//递归分方块
func cutBlock(width: Int, height: Int) {
    if width % height == 0 {
        print("宽:\(width) 高:\(height)")
//        return
    } else {
        let space = width % height
        cutBlock(width: height, height: space)
    }
}
print(cutBlock(width: 1680, height: 640))



//递归函数
func fact(x: Int) -> Int{
    if x == 1 {
        return 1
    }else{
        return x * fact(x: x - 1)
    }
}
print(fact(x: 4))



//找出一个数组中的最小元素
func findMostSmall(arr: Array<Int>) {
    var min = arr[0]
    var min_index = 0
    for i in 1..<arr.count {
        if arr[i] < min {
            min = arr[i]
            min_index = i
        }
    }
    print("最小值\(min), 索引\(min_index)")
}

let arr2 = [4,6,1,88,99,3,2,0,13]
findMostSmall(arr: arr2)


// MARK: - 二分法
// 二分法示例
/*
 1. 设置收尾索引
 2. 通过首尾获取中间索引，取出中间元素对比
 3. 如果相等，直接返回索引
 4. 如果中间值小于a，
 */
func binaryList(list: Array<Int>, item: Int) -> Int? {
    var low = 0
    var high = list.count - 1
    while low <= high {
        let middle = (low + high)/2
        let guess = list[middle]
        if guess == item {
            return middle
        }
        if guess < item {
            low = middle + 1
        }else {
            high = middle - 1
        }
    }
    return nil
}

let arr3 = [1,4,7,9,13,35,78]



func binary(list: Array<Int>, item: Int) -> Int? {
    var low = 0
    var high = list.count - 1
    while low < high {
        let middle = (low + high)/2
        let guess = list[middle]
        if guess == item {
            return middle
        }
        if item < guess {
            high = middle + 1
        }else {
            low = middle + 1
        }
    }
    return nil
}

let index2 = binary(list: arr3, item: 35)
print(index2)
